/LMAR=0/XLINE=3/FONT#0=BAXL30/FONT#1=BAXM30/FONT#2=BAXB30/FONT#3=SUB/FONT#4=SUP/FONT#5=NGR25/FONT#6=NGR20/FONT#7=MATH30/FONT#9=GRK30/FONT#10=MS25/FONT#11=GRFX25/FONT#12=GRFX35
␈↓ ↓H␈↓␈↓ εH␈↓ 91


␈↓ ↓H␈↓α␈↓ ¬{Chapter IV

␈↓ ↓H␈↓α␈↓ βVIMPURE PROGRAMS AND UNCLEAN PROGRAMS


␈↓ ↓H␈↓        Pure␈α
clean␈α∞LISP␈α
programs␈α∞admit␈α
the␈α
elegant␈α∞mathematical␈α
characterization␈α∞described␈α
and
␈↓ ↓H␈↓applied␈α⊂in␈α⊂Chapter␈α∂3.␈α⊂ Specifically,␈α⊂each␈α∂recursively␈α⊂defined␈α⊂pure␈α∂clean␈α⊂LISP␈α⊂function␈α⊂can␈α∂be
␈↓ ↓H␈↓translated␈αinto␈αa␈αfunctional␈αequation␈αand␈αminimization␈αschema␈αin␈αa␈αfirst␈αorder␈αlanguage,␈αand␈αthe
␈↓ ↓H␈↓function and schema can be used to prove that the program admits its extensional specifications.

␈↓ ↓H␈↓        In␈α⊂this␈α∂chapter␈α⊂we␈α∂shall␈α⊂describe␈α∂some␈α⊂additional␈α∂features␈α⊂of␈α∂practical␈α⊂LISP␈α⊂systems␈α∂for
␈↓ ↓H␈↓which␈αgood␈αmathematical␈αcharacterizations␈αhave␈αnot␈α
yet␈αbeen␈αfound.␈α Every␈αcomputation␈αthat␈α
can
␈↓ ↓H␈↓be␈α∂done␈α∂with␈α∂these␈α∂features␈α∂can␈α∂be␈α∂done␈α∂in␈α∂pure␈α∂clean␈α∂LISP,␈α∂but␈α∂nevertheless␈α∂there␈α⊂are␈α∂good
␈↓ ↓H␈↓reasons␈α
for␈α
sometimes␈α
using␈α
these␈α
features.␈α
 We␈α
shall␈α
examine␈α
the␈α
features␈α
themselves␈α
and␈αalso␈α
the
␈↓ ↓H␈↓criteria that determine when they should be used in preference to pure clean LISP.



␈↓ ↓H␈↓1.  ␈↓αSequential (Algol-like) programs.␈↓


␈↓ ↓H␈↓        Sequential␈α
programs␈α
are␈α
impure,␈α
but␈α
can␈α
be␈α
clean␈α
provided␈α
certain␈α
restrictions␈α
are␈α
observed.
␈↓ ↓H␈↓The␈αexternal␈α
notation␈αfor␈αsequential␈α
programs␈αis␈α
adapted␈αfrom␈αthat␈α
of␈αAlgol␈α60.␈α
 We␈αallow␈α
as␈αa
␈↓ ↓H␈↓term an expression of the form

␈↓ ↓H␈↓        ␈↓↓program[<variable list>,<statement list>]␈↓,

␈↓ ↓H␈↓where␈α␈↓↓<variable␈α
list>␈↓␈αis␈α
a␈αlist␈αof␈α
variables␈αlocal␈α
to␈αthe␈α
program,␈αand␈α␈↓↓<statement␈α
list>␈↓␈αis␈α
a␈αlist␈αof␈α
the
␈↓ ↓H␈↓statements␈α
of␈α
the␈αprogram.␈α
 As␈α
in␈αAlgol␈α
60,␈α
the␈αstatements␈α
are␈α
separated␈αby␈α
semicolons,␈α
and␈αany
␈↓ ↓H␈↓statement may be preceded by a label followed by a colon.

␈↓ ↓H␈↓        The statements are of the following kinds:

␈↓ ↓H␈↓        1. Assignment statements of the form

␈↓ ↓H␈↓        ␈↓↓<left hand side> ← <right hand side>␈↓,

␈↓ ↓H␈↓where␈α⊃␈↓↓<left␈α⊃hand␈α⊃side>␈↓␈α⊃is␈α⊃a␈α⊃variable,␈α⊃possibly␈α⊃subscripted,␈α⊃and␈α⊃␈↓↓<right␈α⊃hand␈α⊃side>␈↓␈α⊃is␈α⊃a␈α⊃LISP
␈↓ ↓H␈↓expression that can be evaluated.

␈↓ ↓H␈↓        2. ␈↓αgo to␈↓ statements of the form

␈↓ ↓H␈↓        ␈↓αgo to␈↓↓ a␈↓

␈↓ ↓H␈↓where ␈↓↓a␈↓ is a label or a conditional expression that evaluates to a label.

␈↓ ↓H␈↓        3. A conditional statement which has the form
␈↓ ↓H␈↓␈↓ ¬cCHAPTER IV␈↓ 92


␈↓ ↓H␈↓        ␈↓↓␈↓αif␈↓↓ p1 ␈↓αthen␈↓↓ s1 ␈↓αelse␈↓↓ ␈↓αif␈↓↓ ... ␈↓αelse␈↓↓ ␈↓αif␈↓↓ pn ␈↓αelse␈↓↓ sn␈↓,

␈↓ ↓H␈↓where the ␈↓↓p␈↓'s are propositional expressions having truth values, and the ␈↓↓s␈↓'s are any statements.

␈↓ ↓H␈↓        4. ␈↓αreturn␈↓↓ e␈↓

␈↓ ↓H␈↓where␈α␈↓↓e␈↓␈αis␈αan␈αarbitrary␈αexpression.␈α The␈α
effect␈αof␈αexecuting␈αthis␈αexpression␈αis␈αto␈αreturn␈α
from␈αthe
␈↓ ↓H␈↓program giving the program the value of the expression ␈↓↓e␈↓.

␈↓ ↓H␈↓        As an example, we might write ␈↓↓reverse␈↓ as follows:

␈↓ ↓H␈↓        ␈↓↓reverse u ← ␈↓αprogram␈↓↓[[v];
␈↓ ↓H␈↓↓                v ← ␈↓¬NIL␈↓↓;
␈↓ ↓H␈↓↓        a:      ␈↓αif␈↓↓ ␈↓αn␈↓↓␈α∧u ␈↓αthen␈↓↓ ␈↓αreturn␈↓↓ v;
␈↓ ↓H␈↓↓                v ← ␈↓αa␈↓↓␈α∧u . v;
␈↓ ↓H␈↓↓                u ← ␈↓αd␈↓↓␈α∧v;
␈↓ ↓H␈↓↓                ␈↓αgo to␈↓ a].

␈↓ ↓H␈↓        The internal form of the same program is

␈↓ ↓H␈↓        (DE REVERSE (U) (PROG (V)
␈↓ ↓H␈↓                (SETQ V NIL)
␈↓ ↓H␈↓                A
␈↓ ↓H␈↓                (COND ((NULL U) (RETURN V)))
␈↓ ↓H␈↓                (SETQ V (CONS (CAR U) V))
␈↓ ↓H␈↓                (SETQ U (CDR U))
␈↓ ↓H␈↓                (GO A)
␈↓ ↓H␈↓        ))

␈↓ ↓H␈↓where␈αthe␈αparagraphing␈αis␈αonly␈αfor␈αthe␈αreader's␈αconvenience.␈α Notice␈αthat␈αin␈αinternal␈αform,␈αlabels
␈↓ ↓H␈↓are statements rather than attachments to statements.

␈↓ ↓H␈↓        Here are some ways we might write ␈↓↓append␈↓:

␈↓ ↓H␈↓        ␈↓↓u * v ← ␈↓αprogram␈↓↓[
␈↓ ↓H␈↓↓                ␈↓αreturn␈↓↓ ␈↓αif␈↓↓ ␈↓αn␈↓↓␈α∧u ␈↓αthen␈↓↓ v ␈↓αelse␈↓↓ ␈↓αa␈↓↓␈α∧u . [␈↓αd␈↓↓␈α∧u * v]]␈↓,


␈↓ ↓H␈↓is just a trivial rewrite of the recursive definition.

␈↓ ↓H␈↓        ␈↓↓u * v ← ␈↓αprog␈↓↓ram[w;
␈↓ ↓H␈↓↓                ␈↓αif␈↓↓ ␈↓αn␈↓↓␈α∧u ␈↓αthen␈↓↓ ␈↓αreturn␈↓↓ v;
␈↓ ↓H␈↓↓                w ← ␈↓αa␈↓↓␈α∧u . [␈↓αd␈↓↓␈α∧u * v];
␈↓ ↓H␈↓↓                ␈↓αreturn␈↓↓ w]␈↓


␈↓ ↓H␈↓is␈αalmost␈α
as␈αclose␈α
to␈αthe␈α
pure␈αLISP␈α
form.␈α If␈αwe␈α
want␈αto␈α
replace␈αthe␈α
recursion␈αby␈α
a␈αloop,␈α
we␈αcan
␈↓ ↓H␈↓write
␈↓ ↓H␈↓␈↓ ¬cCHAPTER IV␈↓ 93


␈↓ ↓H␈↓        ␈↓↓u * v ← ␈↓αprog␈↓↓ram[w;
␈↓ ↓H␈↓↓                w ← ␈↓¬NIL␈↓↓;
␈↓ ↓H␈↓↓        a:      ␈↓αif␈↓↓ ␈↓αn␈↓↓␈α∧u ␈↓αthen␈↓↓ ␈↓αgo to* b;
␈↓ ↓H␈↓α                w ← a␈α∧u . w;
␈↓ ↓H␈↓α                u ← d␈α∧u;
␈↓ ↓H␈↓α                go to* a;
␈↓ ↓H␈↓α        b:      if n␈α∧w then return v;
␈↓ ↓H␈↓α                v ← a␈α∧w . v;
␈↓ ↓H␈↓α                ␈↓πT␈↓α ← d␈α∧w;
␈↓ ↓H␈↓α                go to* b]␈↓.


␈↓ ↓H␈↓This corresponds to the recursive program

␈↓ ↓H␈↓        ␈↓↓u * v ← app[u,v,␈↓¬NIL␈↓↓]

␈↓ ↓H␈↓↓        app[u,v,w] ← ␈↓αif␈↓↓ ␈↓αn␈↓↓␈α∧u ␈↓αthen␈↓↓ [␈↓αif␈↓↓ ␈↓αn␈↓↓␈α∧w ␈↓αthen␈↓↓ v ␈↓αelse␈↓↓ app[u,␈↓αa␈↓↓␈α∧w . v,␈↓αd␈↓↓␈α∧w]]
␈↓ ↓H␈↓↓                ␈↓αelse␈↓↓ app[␈↓αd␈↓↓␈α∧u,v,␈↓αa␈↓↓␈α∧u . w]␈↓


␈↓ ↓H␈↓which can save some storage if it is compiled or interpreted without using the stack.
␈↓ ↓H␈↓␈↓ ¬cCHAPTER IV␈↓ 94


␈↓ ↓H␈↓1. Sequential programs

␈↓ ↓H␈↓2. Side effects

␈↓ ↓H␈↓3. Property lists

␈↓ ↓H␈↓4. Input and output